The present invention relates to a computer of the type having a control unit, calculating, or arithmetic-logic unit, input-output unit, the execution of operations in the arithmetic-logic unit, and memories, if required, which are connected with one another for the transmission, processing and storage of sequences, or strings, of characters.
Conventional computers of the above-described type operate according to the stored program principle which goes back to J. v. Neumann. According to this principle, data and program instructions are stored in the form of words in addressable memory cells. Different regions of the memory are generally provided for data and program instructions. The arithmetic unit is generally composed substantially of a plurality of suitably coupled accumulators.
During execution of a program, one instruction is called up at a time and executed; at the same time, an instruction counter is set to the address of the next instruction to be executed. The instructions relate to the exchange of data between memory and arithmetic-logic unit, the execution of operations in the arithmetic-logic unit, and the control of data output. This all is done under the control of the control unit.
The stored program principle implies, in particular, that program instructions are also subjected to logic-arithmetic operations thus permitting the creation of branch programs, recursions, etc. This mode of operation, on which all computers in current use are based, is characterized in that a problem to be treated is divided, during the establishment of the program, into individual serially performed steps. From this linear sequence of steps, the problem is reconstructed by logic interrelationships within the computer.
The above-described mode of operation presents considerable drawbacks despite its wide-spread acceptance. Within a program, there occur dependencies which are hard to differentiate between instructions which are often quite remote from one another. The programs thus become cluttered and even minor changes may result in considerable interference in the program sequence. The indirect addressing of data in conventional computers requires extensive program portions which relate only to data access and to the distribution of memory locations and which generally are more complicated than the actual computing steps. Furthermore, in linear program sequences, the momentary state of the computer gives no indication of which state in the problem being treated has been reached with respect to the logic structure of that problem. Interaction between user and computer is practically impossible.
It therefore follows that it would be advantageous to provide a computer having a new logic organization which permits more simple program designs and direct interaction with a user.
The problems to be treated by computers have a language-logic structure. They can be represented by means of suitably defined logic elements which are linked together by so-called constructors. Generally, various linkages are nested within one another. This results in a branched-out logic structure for the problems to be treated which is called a "tree".
In particular, it is always possible to produce a binary tree which has only simple branches. The logic elements, which may be single or compound, represent the leaves of a tree and are here called atoms, the linkages between the atoms, i.e. the constructors, are at the nodes. Constructors may also link together more complicated structures, so-called subtrees.
Constructors and atoms are preferably encoded in 8-bit quantities (bytes) such that the circuitry can easily distinguish them by testing one bit position, for example.
Generally atoms are formed by one or more bytes. These can be stored in conventionally built-up registers and can be translated easily in standard character set encodings.
The trees per se have a two-dimensional structure, but by various means they can be unequivocally brought into the form of a linear string of characters.
An example of this is shown in FIG. 1.
A node is a point from which there extend two downwardly-directed branches. A point which is connected only to a node is a leaf. In a tree structure of the type shown in FIG. 1, each node constitutes a constructor and each leaf constitutes an atom. A constructor defines the relationship between the two branches extending downwardly therefrom. The expression represented by the illustrated tree structure is linearized, as is known in art, according to the convention that one begins with the highest node, followed by the linearization of the left successor tree and then followed by the linearization of the right successor tree. Linearization of the complete expression simply involves proceeding in the same manner each time a node is encountered.
Furthermore, two successive constructors.: represent a beginning parenthesis, while end parentheses are implied. Thus, the tree structure shown in FIG. 1 can be directly converted to the linearized expression also shown in FIG. 1.
In a machine, each letter, constructor and mathematical symbol will be encoded into a respective byte composed of a selected number, e.g. 8, of binary bits.
The letters, A, B, C, D, E, F are simply encoded into bytes as well as the arithmetic operators. The letters denote variables to be replaced by numbers such that a computation can take place.
The linearization shown in FIG. 1 is called a pre-order linearization. The described linearization of expressions has nothing in common with conventional programming in which there are only linear instruction sequences provided to execute an algorithm. Hereinafter, the term "expressions" is always intended to mean pre-order linearized binary trees.
Proposals have been made, as disclosed, for example, in U.S. Pat. No. 3,646,523 and IEEE Transactions on Computers, Volume C-20, April, 1971, at page 404, for designing computers in which the program is represented in the form of such expressions. The machine language of these computers is based on the known calculus of lambda conversion, described in Church, ANNALS MATH. STUDIES, No. 6, Princeton Univ. Press, 1941. In these known computers the calculating unit is designed in a conventional manner and the tree structure is preformed in the address representation of the control unit. These approaches have been found, however, to result in computers which are relatively very complex. The accommodation of real problems and the desired direct interaction between computer and user is only possible if use is made of special programming measures which nullify the simplicity of this concept.
There exists a known class of programming languages identified as reduction languages, which are described in: John Backus, IBM Research Report RJ 1010, 1972; and John Backus, IBM Research Report RJ 1245,1973, in which the computations specified by a program consist in a transformation of the program representation into a representation of the result by means of reduction steps.